Graafi invariant

Graafi invariant on graafi struktuuri iseloomustava atribuudi arvuline väärtus või niisuguste väärtuste korrastatud kogum, mis ei sõltu graafi tippude märgistatusest ega selle graafilisest kujutisest. Mängib olulist osa graafide isomorfismi tuvastamisel.

Graafi fundamentaalne invariant on tema struktuur kui diskreetse objekti elementide kooslus (organiseeritus) selle elementide seostatuskorra näol. Struktuur kui niisugune ise on esitatav graafina G, kus isomorfsed graafid omavad ühesugust struktuuri. Struktuuri peamisteks karakteristikuteks on selle sümmeetria omadused, mis avalduvad ühesuguste elementide (st tippude, tipupaaride) näol mida rühmateooria aspektist orbiitideks (sh transitiivsuspiirkondadeks, ekvivalentsusklassideks, positsioonideks jm) nimetatakse.

Tipupaarid on eristatavad graafi seosmaatriksi astendamise teel. Korrutada algne seosmaatriks ${\displaystyle E^{1}}$ iseendaga, kus ${\displaystyle E^{1}\cdot E^{1}=E^{2}}$ ning ${\displaystyle E^{n-1}\cdot E^{1}=E^{n}}$ kusjuures iga astme ${\displaystyle n}$ korral fikseerida erinevate binaarmärkide ${\displaystyle e_{i,j}^{n}}$ arv ${\displaystyle p}$ maatriksis ${\displaystyle E^{n}}$, mis reeglina suureneb. Tipupaariorbiitide basil korrastatud korrutis ${\displaystyle E^{n}}$ on isomorfsete graafide täielik invariant ^[1].

Graafi invariandid jagunevad globaalseteks (graafi tervikut iseloomustavateks) ja lokaalseteks (näiteks, üksikuid tippe ja tipupaare iseloomustavateks).